package ArrayList;

import org.junit.Test;

/**
 * @Classname JZ21调整数组顺序使奇数位于偶数前面
 * @Description TODO
 * @Date 2022/12/6 16:17
 * @Created by xjl
 */
public class JZ21调整数组顺序使奇数位于偶数前面 {
    /**
     * @description 使用暴力的方式来实现 开一新的数组 然后在遍历两次的就可以实现  时间是O(n) 但是需要使用的O（n）
      * @param: nums
     * @date: 2022/12/6 16:19
     * @return: int[]
     * @author: xjl
    */
    public int[] exchange(int[] nums) {
        int[] result=new int[nums.length];
        int index=0;
        for (int i:nums){
            if (i%2!=0){
                result[index++]=i;
            }
        }
        for (int i:nums){
            if (i%2==0){
                result[index++]=i;
            }
        }
        return result;
    }

    /**
     * @description 利用双指针+一次遍历  时间是O(n) 但是需要使用的O（n）
      * @param: nums
     * @date: 2022/12/6 16:46
     * @return: int[]
     * @author: xjl
    */
    public int[] exchange3(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1;
        for (int num : nums) {
            if (num % 2 == 1) {
                res[left++] = num;
            } else {
                res[right--] = num;
            }
        }
        return res;
    }

    /**
     * @description 使用的双指针原地交换来实现
      * @param: nums
     * @date: 2022/12/6 16:55
     * @return: int[]
     * @author: xjl
    */
    public int[] exchange4(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // 找到的奇数
            while (left < right && nums[left] % 2 == 1) {
                left++;
            }
            // 找到偶数
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            // 将这两个的奇偶的交换
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }


    /**
     * @description 使用的双指针的方式来实现
     * 时间是n^n
      * @param: nums
     * @date: 2022/12/6 16:20
     * @return: int[]
     * @author: xjl
    */
    public int[] exchange2(int[] nums) {
       for (int i=0;i<nums.length;i++){
           if (nums[i]%2==0){
               int j=i;
               while (j<nums.length){
                   if (nums[j]%2!=0){
                       int tmp=nums[j];
                       nums[j]=nums[i];
                       nums[i]=tmp;
                   }
                   j++;
               }
           }
       }
       return nums;
    }


    @Test
    public void test(){
        int[] nums=new int[]{1,3,2,4,10,9,14,8,3};
        int[] exchange = exchange(nums);
        for (int i:exchange){
            System.out.print(i+" ");
        }
    }
}
